package com.rui.study.algorithm.P_删除二叉搜索树中的节点;

import com.rui.study.algorithm.TreeNode;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2019-01-21 09:41
 **/
public class Solution {

    /**
     * 思路：查找要删除的节点->删除节点，左子树最大节点上升或右子树最小节点上升
     * @param root
     * @param key
     * @return
     */
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root != null) {
            if (key < root.val) {
                root.left = deleteNode(root.left, key);
            } else if (key > root.val) {
                root.right = deleteNode(root.right, key);
            } else {
                root = deleteNode(root);
            }
        }
        return root;
    }

    private TreeNode deleteNode(TreeNode target) {

        TreeNode newTarget;
        if (target.left != null) {
            newTarget = findMaxNode(target.left, true, target);
        } else if (target.right != null) {
            newTarget = findMinNode(target.right, true, target);
        } else {
            newTarget = null;
        }

        // 暂存待删除节点的左节点和右节点
        TreeNode leftNode = target.left;
        TreeNode rightNode = target.right;

        // 新节点的左右子树
        if (newTarget != null) {
            if (leftNode != newTarget) {
                newTarget.left = leftNode;
            }
            if (rightNode != newTarget) {
                newTarget.right = rightNode;
            }
        }

        return newTarget;
    }

    private TreeNode findMaxNode(TreeNode child, boolean isLeft, TreeNode parent) {
        TreeNode max;
        if (child.right != null) {
            max = findMaxNode(child.right, false, child);
        } else {
            max = child;
            if (child.left != null) {   // 有子节点
                if (isLeft) {
                    parent.left = deleteNode(child);
                } else {
                    parent.right = deleteNode(child);
                }
            } else {                    // 无子节点
                if (isLeft) {
                    parent.left = null;
                } else {
                    parent.right = null;
                }
            }
        }
        return max;
    }

    private TreeNode findMinNode(TreeNode child, boolean isRight,  TreeNode parent) {
        TreeNode min;
        if (child.left != null) {
            min = findMinNode(child.left, false, child);
        } else {
            min = child;
            if (child.right != null) {   // 有子节点
                if (isRight) {
                    parent.right = deleteNode(child);
                } else {
                    parent.left = deleteNode(child);
                }
            } else {                    // 无子节点
                if (isRight) {
                    parent.right = null;
                } else {
                    parent.left = null;
                }
            }
        }
        return min;
    }


    public static void main(String[] args) {
        // 构建二叉搜索树
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);

//        TreeNode root = node5;
//        root.left = node3;
//        root.right = node6;
//        node3.left = node2;
//        node3.right = node4;
//        node6.right = node7;

        node3.left = node2;
        node3.right = node4;
        node2.left = node1;

        long begin = System.currentTimeMillis();
        Solution solution未完成 = new Solution();
        TreeNode result = solution未完成.deleteNode(node3, 3);
        long end = System.currentTimeMillis();
        System.out.println("不同的二叉搜索树：" + result + ", 耗时：[" + (end - begin) + "ms]");
    }
}
